// https://leetcode.cn/problems/shortest-bridge/
// Created by ade on 2022/10/25.
//
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector <pair<int, int>> land1;
    vector <vector<int>> vi;
    int len = 0;

    int shortestBridge(vector <vector<int>> &grid) {
        len = grid.size();
        vi.resize(len, vector<int>(len));
        for (int i = 0; i < len; i++) {
            int flag = 0;
            for (int j = 0; j < len; j++) {
                if (grid[i][j] == 0) {
                    vi[i][j] = 1;
                    continue;
                }
                flag = 1;
                dfs(grid, land1, i, j);
                break;
            }
            if (flag) break;
        }
        vector <vector<int>> directions = {{0,  1},
                                           {0,  -1},
                                           {-1, 0},
                                           {1,  0}};
        int steps = 0;
        while (1) {
            vector <pair<int, int>> tmp = {};
            for (int i = 0; i < land1.size(); i++) {
                for (auto &d : directions) {
                    int x = land1[i].first + d[0];
                    int y = land1[i].second + d[1];
                    if (x >= 0 && x < len && y >= 0 && y < len) {
                        if (vi[x][y] == 1) continue;
                        if (grid[x][y] == 1) {
                            cout << "x:" << x << ",y:" << y << endl;
                            return steps;
                        }
                        grid[x][y] = 1;
                        vi[x][y] = 1;
                        tmp.push_back({x, y});
                    }
                }
            }
            steps++;
            land1 = tmp;
            for (int i = 0; i < land1.size(); i++) {
                cout << land1[i].first << "-" << land1[i].second << endl;
            }
            cout << "end" << endl;
        }
    }

    // 只记录边缘的
    void dfs(vector <vector<int>> &grid, vector <pair<int, int>> &land, int i, int j) {
        if (i < 0 || j < 0 || i >= len || j >= len || vi[i][j] == 1 || grid[i][j] == 0) return;
        // 剩下的肯定是为1的
        vi[i][j] = 1;
        if (i + 1 < len && grid[i + 1][j] == 0 || i - 1 >= 0 && grid[i - 1][j] == 0
            || j + 1 < len && grid[i][j + 1] == 0 || j - 1 >= 0 && grid[i][j - 1] == 0)
            land.push_back({i, j});
        dfs(grid, land, i + 1, j);
        dfs(grid, land, i - 1, j);
        dfs(grid, land, i, j + 1);
        dfs(grid, land, i, j - 1);
    }
};

int main() {
    Solution so;
    vector <vector<int>> a = {
            {0, 1, 0},
            {0, 0, 0},
            {0, 0, 1}
    };
    cout << so.
            shortestBridge(a)
         <<
         endl;
    return 0;
}